from random import random
import math

class Player:
    def __init__(self):
        self.name = "Brainiac"
        self.nets = []
        self.reps = []
        self.predicted_hunters = []
        self.actual_hunters = []
        self.trainData = [[]]
        self.setup = False

    def setupData(self,player_reputations):
        self.reps = player_reputations
        self.nets = [NN([4,6,10,5,1]) for x in player_reputations]
        self.trainData = [[] for x in player_reputations]
        self.setup = True

    def align(self,player_reputations):
        sorted_player_reputations = list(zip(player_reputations,[i for i in range(len(player_reputations))]))
        sorted_player_reputations = sorted(sorted_player_reputations,key=lambda x: x[0])
        sorted_reps = list(zip(self.reps,[i for i in range(len(self.reps))]))
        sorted_reps = sorted(sorted_reps,key=lambda x: x[0])
        holes = len(sorted_reps)-len(sorted_player_reputations)
        
        dp = [[0]*(holes+1) for i in range(len(sorted_player_reputations)+1)]
        record = [[[] for j in range(holes+1)] for i in range(len(sorted_player_reputations)+1)]
        for i in range(1,len(sorted_player_reputations)+1):
            if i <= len(sorted_reps):
                dp[i][0] = dp[i-1][0]+(sorted_player_reputations[i-1][0]-sorted_reps[i-1][0]) ** 2
            else:
                dp[i][0] = dp[i-1][0]
        for j in range(1,holes+1):
            for i in range(1,len(sorted_player_reputations)+1):
                cost1 = dp[i-1][j]+(sorted_reps[i+j-1][0]-sorted_player_reputations[i-1][0]) ** 2
                cost2 = dp[i][j-1]
                if cost2 < cost1:
                    dp[i][j] = cost2
                    record[i][j] = record[i][j-1][:]
                    record[i][j].append(i+j-1)
                else:
                    dp[i][j] = cost1
                    record[i][j] = record[i-1][j][:]

        hole_positions = record[len(sorted_player_reputations)][holes]
        
        aligned_nets = [0]*len(sorted_player_reputations)
        for i in range(len(sorted_player_reputations)):
            aligned_nets[sorted_player_reputations[i][1]] = self.nets[sorted_reps[i+sum(map(lambda x: 1 if x <= i else 0,hole_positions))][1]]
        self.nets = aligned_nets        
        self.reps = player_reputations

    def addTrainingData(self,my_normalized_rep,normalized_reps,round_number,m):
        for i in range(len(normalized_reps)):
            self.trainData[i].append([[my_normalized_rep,normalized_reps[i],round_number,m],[]])

    def trainNets(self):
        for i in range(len(self.nets)):
            if len(self.trainData[i]) > 10:
                self.nets[i].train(self.trainData[i][-10:])
            else:
                self.nets[i].train(self.trainData[i])                

    def hunt_choices(self, round_number, current_food, current_reputation, m,
            player_reputations):

        num_players = len(player_reputations)

        if not self.setup:
            self.setupData(player_reputations)
        else:
            self.align(player_reputations)
        
        normalized_reps = normalize(player_reputations)

        sd = sdev(player_reputations)
        my_normalized_rep = current_reputation
        if sd == 0:
            my_normalized_rep = current_reputation-mean(player_reputations)
        else:
            my_normlized_rep = (current_reputation-mean(player_reputations))/sd

        self.addTrainingData(my_normalized_rep,normalized_reps,math.exp(round_number/300),m)

        response_matrix = [[0]*num_players for i in range(num_players)]
        
        for i in range(num_players):
            for j in range(num_players):
                a = i
                b = j
                if b >= a:
                    b += 1
                if b < num_players:
                    response_matrix[i][j] = self.nets[a].propagate([self.reps[b],normalized_reps[a],math.exp(round_number/300),m])[0]
                else:
                    response_matrix[i][j] = self.nets[a].propagate([my_normalized_rep,normalized_reps[a],math.exp(round_number/300),m])[0]                    
                            
        hunters = 0
        for i in range(num_players):
            for j in range(num_players):
                if response_matrix[i][j] > 0.5:
                    hunters += 1
        self.predicted_hunters.append(hunters)
        #hunters += mean([self.actual_hunters[i]-self.predicted_hunters[i] for i in range(len(self.actual_hunters))])

        hunts = m-hunters
        if hunts < 0 or hunts > num_players:
            hunts = 0

        zipped = zip(player_reputations,[i for i in range(num_players)])
        zipped = sorted(zipped,key=lambda x: -x[0])        
        
        hunt_decisions = ['s' for i in range(num_players)]
        for i in range(hunts):
            hunt_decisions[zipped[i][1]] = 'h'
        
        return hunt_decisions

    def hunt_outcomes(self, food_earnings):
        for i in range(len(food_earnings)):
            if food_earnings[i] >= 0:
                self.trainData[i][-1][1].append(1)
            else:
                self.trainData[i][-1][1].append(0)
        self.trainNets()
        
    def round_end(self, award, m, number_hunters):
        self.actual_hunters.append(number_hunters)

    def __str__(self):
        return "Brainiac"

def sigmoid(x):
    return math.tanh(x)

def dsigmoid(y):
    return 1.0 - y ** 2

def mean(xs):
    return sum(xs)/len(xs) if len(xs) > 0 else 0

def sdev(xs):
    if len(xs) < 2:
        return 0
    m = [xs[0]]
    s = 0
    for i in range(1, len(xs)):
        m.append(m[i-1]+(xs[i]-m[i-1])/(i+1))
        s += (xs[i]-m[i-1])*(xs[i]-m[i])
    return math.sqrt(s/(len(xs)-1))

def normalize(xs):
    mu = mean(xs)
    sd = sdev(xs)
    if sd == 0:
        return list(map(lambda x: (x-mu), xs))
    else:
        return list(map(lambda x: (x-mu)/sd, xs))

def featureNormalize(data):
    inputs = len(data[0][0])
    for i in range(inputs):
        xs = [data[j][0][i] for j in range(len(data))]
        xs = normalize(xs)
        for j in range(len(data)):
            data[j][0][i] = xs[j]

def randMatrix(rows, cols, f = lambda x: x-0.5):
    mat = {}
    for i in range(rows):
        for j in range(cols):
            mat[(i,j)] = f(random())
    return mat

class Layer:
    def __init__(self, size):
        self.a = [0.0]*(size+1)
        self.z = [0.0]*(size+1)
        self.z[-1] = 1
        self.a[-1] = 1
    
    def setActivation(self, activation):
        self.z[0:-1] = activation
        self.a[0:-1] = list(map(sigmoid,activation))

class Conn:
    def __init__(self, input_size, output_size):
        self.input_size = input_size
        self.output_size = output_size
        self.w = {(a, b): 0 for a in range(input_size) for b in range(output_size)}
        self.c = {(a, b): 0 for a in range(input_size) for b in range(output_size)}

    def forward(self, a):
        output = [0.0]*self.output_size
        for o in range(self.output_size):
            sum = 0
            for i in range(self.input_size):
                sum += self.w[(i,o)]*a[i]
            output[o] = sum
        return output

    def backward(self, delta,a):
        input = [0.0]*self.input_size
        for i in range(self.input_size):
            sum = 0
            for o in range(self.output_size):
                sum += self.w[(i,o)]*delta[o]
            input[i] = sum*dsigmoid(a[i])
        return input

    def update(self, change, alpha, beta):
        for pair in self.w:
            self.w[pair] += alpha*change[pair]+beta*self.c[pair]
        self.c = change

    def randomize(self):
        self.w = randMatrix(self.input_size,self.output_size)

class NN:
    def __init__(self, layerSizes):
        #activations
        self.a = [Layer(x) for x in layerSizes]

        #weights
        self.w = [Conn(layerSizes[i-1]+1,layerSizes[i]) for i in range(1,len(layerSizes))]

        for conn in self.w:
            conn.randomize()
    
    def propagate(self, inputs):
        if len(inputs) != len(self.a[0].a)-1:
            print(inputs)
            print(self.a[0].a)
            raise ValueError("wrong number of inputs")

        for i in range(len(inputs)):
            self.a[0].setActivation(inputs)

        for i in range(1,len(self.a)):
            self.a[i].setActivation(self.w[i-1].forward(self.a[i-1].a))

        return self.a[-1].a[:-1]

    def backprop(self,targets,alpha,beta):
        if len(targets) != len(self.a[-1].a)-1:
            raise ValueError("wrong number of targets")

        deltas = [[0.0]*len(layer.a) for layer in self.a]
        #output errors
        for i in range(len(targets)):
            error = targets[i]-self.a[-1].a[i]
            deltas[-1][i] = error

        #hidden errors
        for i in range(len(deltas)-2,0,-1):
            for j in range(len(self.a[i].a)):
                deltas[i] = self.w[i].backward(deltas[i+1],self.a[i].a)

        #fix indexing
        deltas.pop(0)

        #update weights
        for i in range(len(self.w)):
            change = {(a,b): 0.0 for a in range(len(self.a[i].a)) for b in range(len(deltas[i]))}
            for j in range(len(self.a[i].a)):
                for k in range(len(deltas[i])):
                    change[(j,k)] = self.a[i].a[j]*deltas[i][k]
            self.w[i].update(change,alpha,beta)

        #find error
        error = 0.0
        for i in range(len(targets)):
            error += 0.5*(targets[i]-self.a[-1].a[i])**2
        return error

    def train(self, trainData, iterations=100, alpha=0.05, beta=0.01):
        for i in range(iterations):
            error = 0.0
            for p in trainData:
                inputs = p[0]
                targets = p[1]
                self.propagate(inputs)
                error += self.backprop(targets,alpha,beta)
            if i % 50 == 0:
                pass
                #print("error =",error)

    def test(self, trainData):
        for p in trainData:
            print(p[0], '->', self.propagate(p[0]))
